//
// Created by dgy on 2022/9/24.
//
#include <cstring>
#include "iostream"
using namespace std;
bool isMatch(string s, string p) {
    int n = s.size(), m = p.size();
    int dp[n + 5][m + 5];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i = 0; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(p[j - 1] != '*') {
                if(i >= 1 && (s[i - 1] == p[j - 1] || p[j - 1] == '.')) dp[i][j] = dp[i - 1][j - 1];
            }
            else {
                if(j >= 2) dp[i][j] |= dp[i][j - 2];
                if(i >= 1 && j >= 2 && (s[i - 1] == p[j - 2] || p[j - 2] == '.')) dp[i][j] |= dp[i - 1][j];
            }
        }
    }
    return dp[n][m];
}
int main(){
    string s="aab";
    string p="c*a*b*";
    bool result=isMatch(s,p);
    cout<<result<<endl;
}
